/**an implementation of LinkedList
 * 
 * @version 1.01
 * @author locphan
 * 
 */
import java.util.*;


public class OurLinkedList < E >  implements Cloneable
{
  // Data Fields
  /** A reference to the head of the list. */
  private Node < E > head = null;

  /** A reference to the end of the list. */
  private Node < E > tail = null;

  /** The size of the list. */
  private int size = 0;

  //Methods
  /** Add an item at the specified index.
      @param index The index at which the object is to be
             inserted
      @param obj The object to be inserted
      @throws IndexOutOfBoundsException if the index is out
              of range (i < 0 || i > size())
   */
  public void add(int index, E obj) 
  {
    listIterator(index).add(obj);
  }
  /**Add an item at the end of the list
   * 
   * @param obj The object to be inserted
   */
  public void add(E obj)
  {
    listIterator(size).add(obj);
  }
  /**Add an item at the beginning of the list
   * 
   * @param obj The object to be added
   */
  public void addFirst(E obj)
  {
     listIterator(0).add(obj);
  }
  /**Add an item at the end of the list
   * 
   * @param obj The object to be added
   * 
   */
  public void addLast(E obj)
  {
     listIterator(size).add(obj);
  }
  /** Get the element at position index.
      @param index Position of item to be retrieved
      @return The item at index
   */
  public E get(int index) 
  {
    return listIterator(index).next();
  }
  /**Check if the list contains an item
   * 
   * @param obj The object to be checked
   * @return True if object is in the list
   *        False otherwise
   */
  public boolean contains(E obj)
  {
     boolean result = false;
     
     ListIterator<E> iterator = listIterator(0);
     
     for(int i=0; i<size;i++)
     {
        if(iterator.next().equals(obj))
        {
           result = true;
           break;
        }     
     }
     
     return result;
  }
  /**Return the first item of the list
   * 
   * @return The first item
   */
  public E getFirst()
  {
     return head.data;
  }
  /**Return the last item of the list
   * 
   * @return The last item
   * 
   */
  public E getLast()
  {
     return tail.data;
  }
  /**Search for an index of item
   * 
   * @param obj The object
   * @return index
   */
  public int indexOf(E obj)
  {
     int result = -1;
     
     ListIterator<E> iter = listIterator(0);
     for(int i=0;i<size;i++)
     {
        if(iter.next().equals(obj))
        {
           result = i;
           break;
        }
     }
     return result;
  }
  /**Return index of the last appearance 
   * of an item in the list 
   * 
   * @param obj The object
   * @return index
   */
  public int lastIndexOf(E obj)
  {
     int result = -1;
     
     ListIterator<E> iter = listIterator(0);
     
     for(int i=0;i<size;i++)
     {
        if(iter.next().equals(obj))
        {
           result = i;
        }
     }
     return result;
  }
  /**Remove item from the list
   * by a given position
   * 
   * @param position index
   * @return Removed item
   */
  public E remove(int position)
  {
     ListIterator<E> iter = listIterator(0);
     E item = null;
     for(int i=0;i<=position;i++)
     {
        item = iter.next();
     }
     
     iter.remove();
     return item;
  }
  /**Remove item from the list
   * by a given sample item
   * 
   * @param obj Sample item
   * @return true if item is successfully removed
   *        false otherwise
   */
  public boolean remove(E obj)
  {
     boolean result = false;
     ListIterator<E> iter = listIterator(0);
     E item = null;
     for(int i=0;i<size;i++)
     {
        item = iter.next();
        if(item.equals(obj))
        {
           result = true;
           break;
           
        }
     }
     
     iter.remove();
     return result;
  }
  /**Replace old item with new item
   * 
   * @param position index of old item
   * @param obj new item
   * @return old item
   */
  public E set(int position, E obj)
  {
     ListIterator<E> iter = listIterator(0);
     E item = null;
     for(int i=0;i<=position;i++)
     {
        item = iter.next();
     }
     iter.set(obj);
     return item;
  }
  /**Return size of the list
   * 
   * @return Size
   */
  public int size()
  {
     return size;
  }
  /**Return the listiterator of this list
   * by a given position
   * 
   * @param i position
   * @return listiterator
   */
  public ListIterator <E> listIterator(int i) 
  {
     return new OurListIter(i);
  }
  /**Return a clone of this class
   * 
   */
  public Object clone()
  {
     OurLinkedList<E> cloned = null;
     try
     {
        cloned = (OurLinkedList<E>) super.clone();
        
     }
     catch(CloneNotSupportedException e)
     {
        e.printStackTrace();
     }
     return cloned;
     
  }
  /**Return a string representation of this class
   *
   */
  public String toString()
  {
     String result = "";
     ListIterator<E> iterator = listIterator(0);
     
     for(int i=0; i<size;i++)
     {
        result += iterator.next()+", ";
        
     }

     return result;
  }
  // Inner Classes

  /** A Node is the building block for a double-linked list. */
  private static class Node < E > {
    /** The data value. */
    private E data;

    /** The link to the next node. */
    private Node < E > next = null;

    /** The link to the previous node. */
    private Node < E > prev = null;

    /** Construct a node with the given data value.
        @param dataItem The data value
     */
    private Node(E dataItem) {
      data = dataItem;
    }
  } //end class Node

  /** Inner class to implement the ListIterator interface. */
  private class OurListIter implements ListIterator < E > {
    /** A reference to the next item. */
    private Node < E > nextItem;

    /** A reference to the last item returned. */
    private Node < E > lastItemReturned;

    /** The index of the current item. */
    private int index = 0;

    /** Construct a OurListIter that will reference the ith item.
        @param i The index of the item to be referenced
     */
    public OurListIter(int i) {
      // Validate i parameter.
      if (i < 0 || i > size) {
        throw new IndexOutOfBoundsException(
            "Invalid index " + i);
      }
      lastItemReturned = null; // No item returned yet.
      // Special case of last item.
      if (i == size) {
        index = size;
        nextItem = null;
      }
      else { // Start at the beginning
        nextItem = head;
        for (index = 0; index < i; index++) {
          nextItem = nextItem.next;
        }
      }
    }

    /** Indicate whether movement forward is defined.
        @return true if call to next will not throw an exception
     */
    public boolean hasNext() {
      return nextItem != null;
    }

    /** Move the iterator forward and return the next item.
        @return The next item in the list
        @throws NoSuchElementException if there is no such object
     */
    public E next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      lastItemReturned = nextItem;
      nextItem = nextItem.next;
      index++;
      return lastItemReturned.data;
    }

    /** Indicate whether movement backward is defined.
        @return true if call to previous will not throw an exception
     */
    public boolean hasPrevious() {
      return (nextItem == null && size != 0)
          || nextItem.prev != null;
    }

    /** Return the index of the next item to be returned by next
            @return the index of the next item to be returned by next
     */
    public int nextIndex() 
    {
      return index;
    }

    /** Return the index of the next item to be returned by previous
           @return the index of the next item to be returned by previous
     */
    public int previousIndex() {
      return index-1;
    }

    /** Move the iterator backward and return the previous item.
        @return The previous item in the list
        @throws NoSuchElementException if there is no such object
     */
    public E previous() {
      if (!hasPrevious()) {
        throw new NoSuchElementException();
      }
      if (nextItem == null) { // Iterator past the last element
        nextItem = tail;
      }
      else {
        nextItem = nextItem.prev;
      }
      lastItemReturned = nextItem;
      index--;
      return lastItemReturned.data;
    }

    /** Add a new item between the item that will be returned
        by next and the item that will be returned by previous.
        If previous is called after add, the element added is
        returned.
        @param obj The item to be inserted
     */
    public void add(E obj) 
    {
      if (head == null) { // Add to an empty list.
        head = new Node < E > (obj);
        tail = head;
      }
      else if (nextItem == head) { // Insert at head.
        // Create a new node.
        Node < E > newNode = new Node < E > (obj);
        // Link it to the nextItem.
        newNode.next = nextItem; // Step 1
        // Link nextItem to the new node.
        nextItem.prev = newNode; // Step 2
        // The new node is now the head.
        head = newNode; // Step 3
      }
      else if (nextItem == null) { // Insert at tail.
        // Create a new node.
        Node < E > newNode = new Node < E > (obj);
        // Link the tail to the new node.
        tail.next = newNode; // Step 1
        // Link the new node to the tail.
        newNode.prev = tail; // Step 2
        // The new node is the new tail.
        tail = newNode; // Step 3
      }
      else { // Insert into the middle.
        // Create a new node.
        Node < E > newNode = new Node < E > (obj);
        // Link it to nextItem.prev.
        newNode.prev = nextItem.prev; // Step 1
        nextItem.prev.next = newNode; // Step 2
        // Link it to the nextItem.
        newNode.next = nextItem; // Step 3
        nextItem.prev = newNode; // Step 4
      }
      // Increase size and index and set lastItemReturned.
      size++;
      index++;
      lastItemReturned = null;
    } // End of method add.
    /** Remove the last item returned. This can only be
     *  done once per call to next or previous.
     *  @throws IllegalStateException if next or previous
     *  was not called prior to calling this method
     */
    
      @Override
      public void remove() throws IllegalStateException
      {
         if(lastItemReturned == null)
            throw new IllegalStateException();
         
         if(head == null)
         {
            head = tail = null;
         }
         else if(nextItem == head)
         {
            head = head.next;
            head.prev = null;   
            nextItem = head;
         }
         else if(nextItem == null)
         {
            tail = tail.prev;
            tail.next = null;
         }
         else
         {
            lastItemReturned.prev.next = lastItemReturned.next;
            lastItemReturned.next.prev = lastItemReturned.prev;
         }
         size--;
         index--;
         lastItemReturned = null;    
      }
      /** Replace the last item returned with a new item. 
       * This can only be done once per call to next 
       * or previous.
       *  
       *  @throws IllegalStateException if next or previous
       *  was not called prior to calling this method
       */
      @Override
      public void set(E o) throws IllegalStateException
      {
         if(lastItemReturned == null)
            throw new IllegalStateException();
         else
         {
            lastItemReturned.data = o;
         }
         
      }   

  }


}
